import java.util.ArrayList;
import java.util.List;

/**
 * @author 支绍昆
 * 2024/4/24
 * 词树 用于在字符串列表搜索
 * 如词字符串列表: sit,down,simple,sin
 * 功能: 查找到左开始匹配到sited最多的词,词列表中元素必须完全匹配. 结果为sit
 * si  -> 无结果
 * sit -> sit
 * sinout  -> sin
 **/
public class CharTreeMap<T> {

    private final CharNode<T> root = new CharNode<T>('-');

    /**
     * 构建词树
     * 输入: sit,down,simple,sin
     * 结果树:
     * d-o-w-n
     * s-i-m-p-l-e
     *    -n
     *    -t
     */
    private void put(String key, T value) {
        this.root.put(key.toCharArray(), value, 0);
    }

    private T leftMatch(String key) {
        return this.root.leftMatch(key.toCharArray(), 0);
    }

    private static class CharNode<T> {
        private final char k;
        private T value;
        private List<CharNode<T>> nextList;

        private CharNode(char content) {
            this.k = content;
        }

        private void put(char[] chars, T value, int curLevel) {
            char curChar = chars[curLevel];
            if (nextList == null) {
                nextList = new ArrayList<>();
            } else {
                for (CharNode<T> next : nextList) {
                    if (next.is(curChar)) {
                        if (curLevel < (chars.length - 1)) {
                            next.put(chars, value, curLevel + 1);
                        } else {
                            next.value = value;
                        }
                        return;
                    }
                }
            }
            //如果当前内容不存在-新建
            CharNode<T> newNode = new CharNode<T>(curChar);
            nextList.add(newNode);
            if (curLevel < (chars.length - 1)) {
                newNode.put(chars, value, curLevel + 1);
            } else {
                newNode.value = value;
            }
        }

        private T leftMatch(char[] chars, int curLevel) {
            if (nextList == null) {
                return value;
            }
            if (curLevel > (chars.length - 1)) {
                return value;
            }
            char curChar = chars[curLevel];
            for (CharNode<T> next : nextList) {
                if (next.is(curChar)) {
                    if (curLevel <= (chars.length - 1)) {
                        T result = next.leftMatch(chars, curLevel + 1);
                        if (result != null) {
                            return result;
                        } else {
                            break;
                        }
                    }
                }
            }
            return value;
        }

        private boolean is(char c) {
            return k == c;
        }
    }

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("sited");
        list.add("sit");
        list.add("sin");
        list.add("south");
        list.add("charTree");
        list.add("demo");
        CharTreeMap<String> charTree = new CharTreeMap<String>();
        list.forEach(e -> charTree.put(e, e));

        String value = charTree.leftMatch("south1");
        System.out.println(value);
        System.out.println("done!");
    }

}
